Link to this headingSchnorr’s identification protocol

This is one of the most basic Protocols to prove that they know the Discrete logarithm secret.

Math Proof:

Y = g^X
B = g^A 

Z = A + CX

\\~\\

\begin{aligned}
g^Z & = BY^C \\
    & = g^A * (g^X)^C \\
\end{aligned}
Variations:

Slim Version: Prover doesn’t send the shared_c and instead the verifier generates it.
Subtract Version: Use z = r - x*c and g^z * h^c = u rather than z = r + x*c and g^z = u * h^c
Subtract & Derive: Use z = r - x*c and g^z * h^c = u rather than z = r + x*c and g^z = u * h^c. Also only send shared_c and shared_z. shared_u is generated from u = g^z * h^c and then the hash is calculated with the generated shared_u and the prover_shared_c and the verifier_shared_c are compared.

Link to this headingMultiplicative Protocol
Interactive Protocol:
from Crypto.PublicKey import DSA
import secrets

def prover_step1(generator_g, mod_q, secret_x):
	#Prover chooses the random secret x and generates the g^x -> h
	#From DSA private key
	shared_h = pow(generator_g, secret_x, mod_q)

	#Prover then chooses another random secret r and generates the g^r -> u
	secret_r = 0
	while secret_r == 0:
		secret_r = secrets.randbelow(mod_q)

	shared_u = pow(generator_g, secret_r, mod_q)

	return [secret_r, shared_h, shared_u]


def verifer_step2(shared_u, shared_h, mod_q):
	#Check not zero or infinity point
	assert shared_u != 0
	assert shared_h != 0

	#Check that output is in the group
	assert shared_u > 0 and shared_u < mod_q
	assert shared_h > 0 and shared_h < mod_q

	#Generate a random c to send to prover
	random_c = 0
	while random_c == 0:
		random_c = secrets.randbelow(mod_q)

	return random_c

def prover_step3(secret_r, secret_x, random_c):
	#Prover computes z = r + x * c. and sends to Verifier
	return secret_r + secret_x * random_c


def verifier_step4(generator_g, shared_z, mod_q, shared_u, shared_h, random_c):
	#Verifier Checks that g^z = u* h^c
	assert (shared_z % mod_q) != 0

	right_side = pow(generator_g, shared_z, mod_q)
	left_side = (shared_u * pow(shared_h, random_c, mod_q)) % mod_q
	print(f"right_side:{right_side}")
	print(f"left_side:{left_side}")

	assert right_side == left_side

	return True

if __name__ == "__main__":
	## Setup 
	print("Generating Key")
	private_key = DSA.generate(2048)

	mod_q, subgroup_order, generator_g = private_key.domain()
	secret_x = private_key.x

	#First Step by Prover
	secret_r, shared_h, shared_u = prover_step1(generator_g, mod_q, secret_x)
	print("Finish Step 1")


	#Send the shared_h, shared_u to the verifier
	random_c = verifer_step2(shared_u, shared_h, mod_q)
	print("Finish Step 2")


	#Send the random_c to the prover
	shared_z = prover_step3(secret_r, secret_x, random_c)
	print("Finish Step 3")


	#Final Verication from the Verifier
	print(f"Verifer returned: {verifier_step4(generator_g, shared_z, mod_q, shared_u, shared_h, random_c)}")
Non-Interactive Protocol:
from Crypto.PublicKey import DSA
import secrets
import hashlib

def prover_step1(generator_g, mod_q, secret_x, hash_obj=hashlib.sha256()):
	#Prover chooses the random secret x and generates the g^x -> h
	#From DSA private key
	shared_h = pow(generator_g, secret_x, mod_q)

	#Prover then chooses another random secret r and generates the g^r -> u
	secret_r = 0
	while secret_r == 0:
		secret_r = secrets.randbelow(mod_q)

	shared_u = pow(generator_g, secret_r, mod_q)


	#Use the Hash to generate the random c that is specific to the input varables
	input_str = str(generator_g) + "|" + str(mod_q) + "|" + str(shared_h) + "|" + str(shared_u)
	hash_obj.update(input_str.encode("utf8"))
	hash_int = int.from_bytes(hash_obj.digest(), byteorder='little')
	random_c = hash_int

	#Generate Random Z from z = r + x * c
	shared_z = secret_r + secret_x * random_c

	return [random_c, shared_h, shared_u, shared_z]


def verifer_step2(generator_g, shared_z, mod_q, shared_u, shared_h, random_c, hash_obj=hashlib.sha256()):
	#Check not zero or infinity point
	assert shared_u != 0
	assert shared_h != 0

	#Check that output is in the group
	assert shared_u > 0 and shared_u < mod_q
	assert shared_h > 0 and shared_h < mod_q

	#Check Z is not zero
	assert (shared_z % mod_q) != 0

	#Have the Verifier compute the hash and dont trust the sent hash
	input_str = str(generator_g) + "|" + str(mod_q) + "|" + str(shared_h) + "|" + str(shared_u)
	hash_obj.update(input_str.encode("utf8"))
	hash_int = int.from_bytes(hash_obj.digest(), byteorder='little')
	random_c = hash_int

	#Verifier Checks that g^z = u * h^c
	right_side = pow(generator_g, shared_z, mod_q)
	left_side = (shared_u * pow(shared_h, random_c, mod_q)) % mod_q
	print(f"right_side:{right_side}")
	print(f"left_side:{left_side}")

	assert right_side == left_side

	return True


if __name__ == "__main__":
	## Setup 
	print("Generating Key")
	private_key = DSA.generate(2048)

	mod_q, subgroup_order, generator_g = private_key.domain()
	secret_x = private_key.x

	#First Step by Prover
	random_c, shared_h, shared_u, shared_z = prover_step1(generator_g, mod_q, secret_x)
	print("Finish Step 1")

	#Final Verication from the Verifier
	print(f"Verifer returned: {verifer_step2(generator_g, shared_z, mod_q, shared_u, shared_h, random_c)}")
Link to this headingAdditive Protocol
Interactive Protocol:
from Crypto.PublicKey import DSA
import secrets

def prover_step1(generator_g, mod_q, secret_x):
	#Prover chooses the random secret x and generates the g*x -> h
	#From DSA private key
	shared_h = (generator_g * secret_x) % mod_q

	#Prover then chooses another random secret r and generates the g*r -> u
	secret_r = 0
	while secret_r == 0:
		secret_r = secrets.randbelow(mod_q)

	shared_u = (generator_g * secret_r) % mod_q

	return [secret_r, shared_h, shared_u]


def verifer_step2(shared_u, shared_h, mod_q):
	#Check not zero or infinity point
	assert shared_u != 0
	assert shared_h != 0

	#Check that output is in the group
	assert shared_u > 0 and shared_u < mod_q
	assert shared_h > 0 and shared_h < mod_q

	#Generate a random c to send to prover
	random_c = 0
	while random_c == 0:
		random_c = secrets.randbelow(mod_q)

	return random_c

def prover_step3(secret_r, secret_x, random_c):
	#Prover computes z = r + x * c. and sends to Verifier
	return secret_r + secret_x * random_c


def verifier_step4(generator_g, shared_z, mod_q, shared_u, shared_h, random_c):
	#Verifier Checks that g*z = u* h^c
	assert (shared_z % mod_q) != 0

	right_side = (generator_g * shared_z) % mod_q
	left_side = (shared_u + ((shared_h * random_c) % mod_q)) % mod_q
	print(f"right_side:{right_side}")
	print(f"left_side:{left_side}")

	assert right_side == left_side

	return True

if __name__ == "__main__":
	## Setup 
	print("Generating Key")
	private_key = DSA.generate(2048)

	mod_q, subgroup_order, generator_g = private_key.domain()
	secret_x = private_key.x

	#First Step by Prover
	secret_r, shared_h, shared_u = prover_step1(generator_g, mod_q, secret_x)
	print("Finish Step 1")


	#Send the shared_h, shared_u to the verifier
	random_c = verifer_step2(shared_u, shared_h, mod_q)
	print("Finish Step 2")


	#Send the random_c to the prover
	shared_z = prover_step3(secret_r, secret_x, random_c)
	print("Finish Step 3")


	#Final Verication from the Verifier
	print(f"Verifer returned: {verifier_step4(generator_g, shared_z, mod_q, shared_u, shared_h, random_c)}")
Non-Interactive Protocol:
from Crypto.PublicKey import DSA
import secrets
import hashlib

def prover_step1(generator_g, mod_q, secret_x, hash_obj=hashlib.sha256()):
	#Prover chooses the random secret x and generates the g^x -> h
	#From DSA private key
	shared_h = (generator_g * secret_x) % mod_q

	#Prover then chooses another random secret r and generates the g^r -> u
	secret_r = 0
	while secret_r == 0:
		secret_r = secrets.randbelow(mod_q)

	shared_u = (generator_g * secret_r) % mod_q


	#Use the Hash to generate the random c that is specific to the input variables
	input_str = str(generator_g) + "|" + str(mod_q) + "|" + str(shared_h) + "|" + str(shared_u)
	hash_obj.update(input_str.encode("utf8"))
	hash_int = int.from_bytes(hash_obj.digest(), byteorder='little')
	random_c = hash_int

	#Generate Random Z from z = r + x * c
	shared_z = secret_r + secret_x * random_c

	return [random_c, shared_h, shared_u, shared_z]


def verifer_step2(generator_g, shared_z, mod_q, shared_u, shared_h, random_c, hash_obj=hashlib.sha256()):
	#Check not zero or infinity point
	assert shared_u != 0
	assert shared_h != 0

	#Check that output is in the group
	assert shared_u > 0 and shared_u < mod_q
	assert shared_h > 0 and shared_h < mod_q

	#Check Z is not zero
	assert (shared_z % mod_q) != 0

	#Have the Verifier compute the hash and dont trust the sent hash
	input_str = str(generator_g) + "|" + str(mod_q) + "|" + str(shared_h) + "|" + str(shared_u)
	hash_obj.update(input_str.encode("utf8"))
	hash_int = int.from_bytes(hash_obj.digest(), byteorder='little')
	random_c = hash_int

	#Verifier Checks that g^z = u * h^c
	right_side = (generator_g * shared_z) % mod_q
	left_side = (shared_u + ((shared_h * random_c) % mod_q)) % mod_q
	print(f"right_side:{right_side}")
	print(f"left_side:{left_side}")

	assert right_side == left_side

	return True


if __name__ == "__main__":
	## Setup 
	print("Generating Key")
	private_key = DSA.generate(2048)

	mod_q, subgroup_order, generator_g = private_key.domain()
	secret_x = private_key.x

	#First Step by Prover
	random_c, shared_h, shared_u, shared_z = prover_step1(generator_g, mod_q, secret_x)
	print("Finish Step 1")

	#Final Verication from the Verifier
	print(f"Verifer returned: {verifer_step2(generator_g, shared_z, mod_q, shared_u, shared_h, random_c)}")
Link to this headingPossible Security Issues
Input validation: Insure checks for valid transmitted values

Implicit Trust of Prover:

- Ensure generator_g and mod_q are valid known values

- recalculate and check the random_c from the hashed values

Missing Values:

- if shared_h or shared_u are missing its a major issue

- if generator_g or mod_q are missing it might be an issue

Weak Randomness:

- If there are two separate verifications with the same secret_r with different data this can leak the secret_x. https://www.zkdocs.com/docs/zkdocs/zero-knowledge-protocols/schnorr/

Replay Attacks: Ensure there is a ID to both the verifier and prover to prevent replay attacks
Link to this headingReused r attack
x = \dfrac{z_1 - z_2}{c_1 - c_2}
Link to this headingWeak Randomness Attack
If you use a weak random function you can prove that you know a secret key even though you dont.
import hashlib

#Lets take a random public Key that we dont know the private key for
public_key1 = secrets.randbits(128)

#lets assume that the hash function uses the hash of the public key
random_c = sha1(public_key1).digest()

#Lets use the random Z
random_z = secrets.randbits(128)

fake_privatekey = pow((pow(generator_g, random_z, mod_q) / public_key1), (1/random_c), mod_q)

Link to this headingReconstructing Public Key from Signatures